package arrAndstr;

import java.util.Arrays;
import java.util.Comparator;

/*
    452. 用最少数量的箭引爆气球
    排序+贪心
        知道保证前面打破的气球仍能被打破，则只需要一次
 */
public class T452 {

    public static void main(String[] args) {
        int[][] points = new int[][]{
                {9, 12}, {1, 10}, {4, 11}, {8, 12}, {3, 9}, {6, 9}, {6, 7}
        };
        findMinArrowShots(points);
    }


    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return Integer.compare(o1[0], o2[0]);
                }
                return Integer.compare(o1[1], o2[1]);
            }
        });

        int result = 1;
        int rightRange = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > rightRange) {
                result++;
                rightRange = points[i][1];
            }
            if (points[i][1] < rightRange) {
                rightRange = points[i][1];
            }
        }

        System.out.println(result);
        return result;
    }
}
